#include <vector>
#include <iostream>
#include <algorithm>

struct Task{
	int id;
	int d;
	int w;
	bool selected;
};

struct TaskComp {
	enum Strategy {by_penalty, by_earliness_deadline};
	Strategy strategy;
	bool operator() ( const Task& lhs, const Task& rhs) { 
		if (strategy == by_penalty)
			return lhs.w > rhs.w; 
		else if (strategy == by_earliness_deadline) {
			if (lhs.selected == true && rhs.selected == false)
				return true;
			else if (lhs.selected ==false && rhs.selected == true)
				return false;
			else {
				return lhs.d < rhs.d;
			}
		}
	}
	TaskComp(Strategy s) : strategy(s) {}
};

void unit_task_sche(std::vector<Task> & tasks){
	std::sort(tasks.begin(), tasks.end(), TaskComp(TaskComp::by_penalty));
	const int n = tasks.size();
	std::vector<int> c(n); //capacity
	int limit = -1; //tasks with deadline equals to limit are full
	for (int i = 0; i < n; ++i) {
		if ( tasks[i].d > limit ) {
			tasks[i].selected = true;
			for ( int j = tasks[i].d - 1; j < n; ++j){ //d[i]>=1 -> j>=0
				++c[j];
				if (c[j] == j+1)
					limit = j+1;
			}
		}
	}
	std::sort(tasks.begin(), tasks.end(), TaskComp(TaskComp::by_earliness_deadline));
}

void test_unit_task_sche (int * da, int * wa, int n){
	std::vector<Task> tasks(n);
	for (int i = 0; i < n; ++i){
		tasks[i].id = i;
		tasks[i].d = da[i];
		tasks[i].w = wa[i];
		tasks[i].selected = false;
	}
	std::cout << "Scheduling ... \n";
	unit_task_sche(tasks);
	for ( int i = 0; i < n; ++i) {
		if (tasks[i].selected)
			std::cout << "task " << tasks[i].id << "(" << tasks[i].d << "," << tasks[i].w << ")" << " is selected\n";
	}
}

void test_unit_task_scheduling () {
	int da[] = {4, 2, 4, 3, 1, 4, 6};
	int wa[] = {70, 60, 50, 40, 30, 20, 10};
	test_unit_task_sche(da, wa, sizeof(da)/sizeof(int));

	int wb[sizeof(wa)/sizeof(int)];
	for (int i = 0; i < sizeof(wa)/sizeof(int); ++i)
		wb[i] = 80 - wa[i];
	test_unit_task_sche(da, wb, sizeof(da)/sizeof(int));
}

